package codeTop;

import java.util.HashMap;
import java.util.Map;

public class q146 {
    class LRUCache {

        class Node {
            int key;
            int value;
            Node prev;
            Node next;
            public Node(int key,int value) {
                this.key = key;
                this.value = value;
            }
            public Node(){}
        }
        Map<Integer,Node> map;
        Node head;
        Node tail;
        int size;
        int capacity;
        public LRUCache(int capacity) {
            head = new Node();
            tail = new Node();
            head.next = tail;
            this.capacity = capacity;
            size = 0;
            map = new HashMap<>(capacity);
        }

        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            remove(node);
            addFirst(node);
            return node.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                map.get(key).value = value;
                remove(map.get(key));
                addFirst(map.get(key));
            }else {
                if (size==capacity) {
                    map.remove(tail.prev.key);
                    remove(tail.prev);
                    size--;
                }
                Node node = new Node(key,value);
                map.put(key,node);
                addFirst(node);
                size++;
            }
        }

        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        public void addFirst(Node node) {
            node.prev = head;
            node.next = head.next;
            node.prev.next = node;
            node.next.prev = node;
        }
    }

    class LRUCacheWithTime {

        class Node {
            int key;
            int value;
            long expireTime;
            Node prev;
            Node next;
            public Node(int key,int value,long expireTime) {
                this.key = key;
                this.value = value;
                this.expireTime = expireTime;
            }
            public Node(){}
        }

        Node head;
        Node tail;
        long ttl;
        int size;
        int capacity;
        Map<Integer,Node> map;
        public LRUCacheWithTime(int capacity,long ttl) {
            this.capacity = capacity;
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            size = 0;
            this.ttl = ttl;
            map = new HashMap<>(capacity);
        }

        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            if (isExpired(node)) {
                remove(node);
                map.remove(key);
                return -1;
            }
            remove(node);
            addFirst(node);
            return node.value;
        }

        public void put(int key, int value) {
            long time = System.currentTimeMillis()+ttl;
            if (map.containsKey(key)) {
                map.get(key).value = value;
                map.get(key).expireTime = time;
                remove(map.get(key));
                addFirst(map.get(key));
            }else {
                if (size!=capacity) {
                    Node node = new Node(key, value, time);
                    map.put(key,node);
                    addFirst(node);
                    size++;
                }else {
                    Node temp = tail.prev;
                    while (temp!=head&&isExpired(temp)) {
                        map.remove(temp.key);
                        size--;
                        temp = temp.prev;
                        remove(temp.next);
                    }
                    if (size==capacity) {
                        map.remove(tail.prev.key);
                        remove(tail.prev);
                        Node node = new Node(key, value, time);
                        map.put(key,node);
                        addFirst(node);
                    }
                }
            }
        }

        public boolean isExpired(Node node) {
            return node.expireTime < System.currentTimeMillis();
        }

        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        public void addFirst(Node node) {
            node.prev = head;
            node.next = head.next;
            node.prev.next = node;
            node.next.prev = node;
        }
    }
}
